None.
The present invention relates to apparatus and methods for encoding information to reduce the probability of errors in the transmission and/or recording (storage) of the information. More specifically, the present invention relates to the use of coset partitioning and trellis codes to reduce the probability that transition jitter will cause one allowed sequence to be decoded as another allowed sequence. While not limited as such, the present invention has particular application to magnetic recording.
There are many applications where a sender communicates to a receiver over a noisy channel. Often, some sequences are more likely to be corrupted by noise than other sequences. On the other hand, it is desirable to allow the sender to transmit completely arbitrary messages. This dilemma is solved by encoding arbitrary messages into constrained messages that are well-adapted to the channel. A constrained encoder and its complementary constrained decoder together constitute a constrained code.
A specific application where constrained codes are needed is that of data storage. Data being recorded on a storage medium (to be retrieved by a user at some later time) can be regarded as a noisy communication channel, where recording is viewed as xe2x80x9csendingxe2x80x9d and retrieval (or xe2x80x9cread backxe2x80x9d) is viewed as xe2x80x9creceiving.xe2x80x9d This applies to virtually all current and proposed recording technologies: magnetic, optical. magneto-optical, holographic, etc.
In magnetic recording, various sources of noise can corrupt accurate information (for example, thermal noise, interference, and media noise arising from sources such as jitter, DC erase noise and pulse width/height modulation). Media noise is the dominant source of noise in many current recording systems. Media noise is usually treated as highly correlated non-stationary noise added to the read-back signal. xe2x80x9cTransition jitterxe2x80x9d is the dominant component of media noise and affects the position of transitions. As shown in FIG. 1, media granularity and micromagnetic interactions in magnetic recording media 101 can produce irregular transitions, thus shifting an average transition position 102 from its nominal transition position 104. The resulting transition jitter 106 can be treated as a stationary additive disturbance to transition position. In uncoded recording, if a transition point shifts by more than one half bit cell, then an error will occur.
As seen in FIG. 2, in some magnetic recordings, digitalization of the recorded data (magnetic track 202) can be portrayed in a non return to zero inverted (xe2x80x9cNRZIxe2x80x9d) mode 204xe2x80x94a xe2x80x981xe2x80x99 can be recorded (that is, xe2x80x9csentxe2x80x9d) as a change in magnetic polarity, and a xe2x80x980xe2x80x99 recorded (xe2x80x9csentxe2x80x9d) as the absence of a change in magnetic polarity. For retrieval of the information (detection 206), 1""s are detected by magnetic flux, but 0""s are detected indirectly: the number of 0""s in between two 1""s is inferred by information provided by a clock. To prevent loss of clock synchronization, it is desirable that strings of consecutive 0""s not be too long. To prevent intersymbol interference (that is, interference between two consecutive 1""s), it is also desirable that strings of consecutive 0""s not be too short. To reduce the chance of these types of errors, messages can be recorded that satisfy a run-length-limited (RLL) constraint 302, an example of which is shown in FIG. 3.
Alternatively, the length of a string of pulses can be portrayed as binary 1""s or 0s which represent magnetization orientations. Such a non return to zero (xe2x80x9cNRZxe2x80x9d) portrayal provides another time related sequencing of the recorded data.
This requires the construction of an encoder which encodes arbitrary binary sequences into sequences that obey a specific RLL constraint. It is important that the encoder encode data at a high rate, that the decoder not propagate channel errors, and that the complexity of encoding and decoding be low.
Using the non return to zero (xe2x80x9cNRZxe2x80x9d) method of digitalizing recorded data, a method analogous to the NRZI method, the signaling scheme used in saturation magnetic recording can be characterized as pulse amplitude modulation (PAM). The PAM channel has a constellation of two symbols, corresponding to a single bit cell magnetized in either the up-track or down-track direction. As illustrated in FIG. 4, the recording media is divided into a series of xe2x80x9cbit cellsxe2x80x9d 402. The symbol value is recorded as the magnetization state of each bit cell 402. Consequently, each bit cell 402 is either a +M magnetization bit cell 404 (corresponding to a binary xe2x80x9c0xe2x80x9d) or a xe2x88x92M magnetization bit cell 406 (corresponding to a binary xe2x80x9c1xe2x80x9d). There are compelling physical reasons to restrict the signaling to saturation recording. However, the PAM symbol system has only two symbols, which traditionally has restricted the available encoding schemes. As discussed in more detail below a two symbol constellation has generally precluded traditional application of a trellis coded modulation scheme.
Earlier systems have attempted to use various schemes to enhance the effectiveness of their codes. For example, others have developed codes corresponding to a partition of the channel constellation into two cosets. This appears to have markedly reduced the effectiveness of the codes used. See, for example, C. Heegard, xe2x80x9cTrellis codes for recording,xe2x80x9d in Proc. IEEE Mil. Comm. Conf., 1988; and M. Belongie, xe2x80x9cRunlength codes based on variable length graphs.,xe2x80x9d Ph.D. thesis, Cornell University, January 1992; both of which are incorporated herein by reference.
Trellis coded modulation (TCM) have been attempted as well. TCM schemes combine the functions of modulation and coding by mapping user data onto a constrained sequence of symbols. TCM schemes are a vital component of many communications systems. However, there is no straightforward way to apply TCM (as proposed in earlier systemsxe2x80x94see, for example, G. Ungerboeck, xe2x80x9cTrellis-coded modulation with redundant signal sets,xe2x80x9d IEEE Commun. Mag., vol. 25. no. 2, pp. 5-11 1987; incorporated herein by reference in its entirety) to a PAM scheme where the constellation is restricted to just two symbols. Other TCM schemes for magnetic recording have been proposed. These include Wolf-Ungerboeck codes and matched spectral null (MSN) codes. See, for example; J. K. Wolf and G. Ungerboeck, xe2x80x9cTrellis codes for partial response channels,xe2x80x9d IEEE Trans. Commun., vol. 34, no. 8 1986; and R. Karabed and P. H. Siegel. xe2x80x9cMatched spectral null codes for partial-response channels,xe2x80x9d IEEE Trans. Inform. Theory, vol. 37, no. 3 1991; both incorporated herein by reference. These schemes use a state machine to constrain sequences of transmitted symbols. However, they take an approach which is rather different from classical TCM.
A code which ensures that one allowed sequence cannot be mapped to another by a small (mean-squared) shift of the positions of the written transitions should improve immunity to transition jitter. Moreover, the use of a code in which cosets are defined by their spatial or temporal relationship rather than their relationship in amplitude and/or phase would prove a significant advancement in the art.
The present invention is an encoding method and apparatus which allows data to be transmitted more reliably on certain communications and/or recording channels, especially channels where the communications medium can only support a set of discrete states, including data storage on magnetic and optical media. The invention involves the application of established methods of trellis coded modulation to communications systems where the medium can support only a small number of states and thus the channel alphabet is restricted.
The signaling used in saturation magnetic recording can be described as pulse width modulation (xe2x80x9cPWMxe2x80x9d). A continuous range of magnet lengths are defined between a minimum length (the smallest magnet length that can be written) and a maximum length (the longest magnet that can be read without losing clock synchronization). The recorded magnets are then partitioned into cosets according to the position of the last transition in each magnet. A finite state convolutional encoder can be used to constrain the sequence of magnet cosets.
Instead of using these variable length symbols, however, the code is expressed in terms of a synchronous PAM channel, in which two consecutive transitions define a magnet. Using this expression, the code constraint on transition position is an equivalent constraint on magnet length. An appropriate encoder is created to map user data to a constrained sequence. A Viterbi detector, which reflects the code constraints, has states which are the product of the channel states of a conventional PRML detector and the states of the constraint graph. Because of the constraints, only a small subset of all branches are permitted at each resulting trellis update. A conventional sliding block decoder can be used to map the detected data back to user data. In this way, a complete coded recording system can be constructed using standard building blocks of existing PRML channels, namely, a finite state encoder, a Viterbi detector and a sliding block decoder.